【题解】 [SDOI2008]Sandy的卡片 后缀数组.SA luoguP2463 | Qiuly's blog!

【题解】 [SDOI2008]Sandy的卡片 后缀数组.SA luoguP2463

Posted on | Edited on | In | Comments:

后缀数组，我们可以先将所有的卡片连成一个串，每一个卡片数列之间用一个极大数分开保证不出锅。然后的话，对于相同的定义有些鬼，使得我们不能直接做 $SA$ ，这个时候我们将所有的卡片数列的值都转换为当前位置减去上个位置的值即可。

然后就是统计答案，我们二分这个最长公共子序列的长度，每一次去判断是否合法。怎么判断呢？首先对于 $height$ 数组，如果要满足要求的话选取的这一段的 $height$ 数组的值都不能小于当前的 $mid$ ，这是显然的。

怎么确保我们将所有的卡片数列都选了呢？直接开一个 $vis​$ 数组即可，然后在碰到不合法的地方(也就是 $height[i]​$ 小于了 $mid​$ )全部清空即可。

最后如何判断当前的 $mid$ 是否合法呢？很显然，只有在所有的卡片数列都成功选择的情况下就合法了。我们用一个栈维护 $vis$ ，清空方便，然后当栈顶为卡片序列数的时候，也就是所有的卡片序列都选择的时候，$mid$ 就合法了。

然后有个悲催的事情，窝打二分的时候……打成了这样： 

1
2
3
4
5
while(l<=r) {
    int mid=(l+r)>>1;
    if(check(mid)) ans=mid,l=mid+1;
    r=mid-1;
}

很显然，$r$ 前面应该要有 $else$ ，但是窝看了一晚上都没看出来…….

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=2e6+7;
const int M=5e2+7;
const int G=5e3+7;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

namespace SA {
    int n,m,S[N],sa[N],height[N],x[N],y[N],hep[N];
    inline void pre_sa() {
        ++m;
        for(int i=1;i<=n;++i) x[i]=S[i];
        for(int i=1;i<=n;++i) hep[x[i]]++;
        for(int i=1;i<=m;++i) hep[i]+=hep[i-1];
        for(int i=n;i>=1;--i) sa[hep[x[i]]--]=i;
        for(int w=1,p=0;m=p,p<n;w<<=1) {
            p=0;
            for(int i=1;i<=w;++i) y[++p]=n-w+i;
            for(int i=1;i<=n;++i) if(sa[i]>w) y[++p]=sa[i]-w;
            for(int i=0;i<=m;++i) hep[i]=0;
            for(int i=1;i<=n;++i) hep[x[i]]++;
            for(int i=1;i<=m;++i) hep[i]+=hep[i-1];
            for(int i=n;i>=1;--i) sa[hep[x[y[i]]]--]=y[i];
            swap(x,y);
            x[sa[1]]=p=1;
            for(int i=2;i<=n;++i)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?p:++p;
        }return;
    }
    inline void pre_height(){
        for(int i=1;i<=n;++i)x[sa[i]]=i;
        int k=0;
        for(int i=1;i<=n;++i){
            k-=k>0;
            int j=sa[x[i]-1];
            while(j+k<=n&&i+k<=n&&S[j+k]==S[i+k])++k;
            height[x[i]]=k;
        }return;
    }
}using namespace SA;

int vis[G],stack[G],top;
int num,len[G],id[N],a[G][M];

inline bool check(int x) {
    while(top) vis[stack[top--]]=0;
    for(int i=1;i<=n;++i) {
        if(height[i]<x) {
            while(top) vis[stack[top--]]=0;
        }
        if(!vis[id[sa[i]]]) {
            stack[++top]=id[sa[i]],vis[id[sa[i]]]=true;
            if(top==num) return true;
        }
    }return false;
}
int main() {
    IN(num);
    int mx=-inf,mi=inf,l=0,r=inf;
    for(int i=1;i<=num;++i) {
        IN(len[i]),r=min(r,len[i]-1);
        for(int j=1;j<=len[i];++j) {
            IN(a[i][j]);
            if(j!=1)mx=max(mx,a[i][j]-a[i][j-1]);
        }
    }
    for(int i=1;i<=num;++i) {
        for(int j=2;j<=len[i];++j)
            S[++n]=a[i][j]-a[i][j-1],id[n]=i,mi=min(mi,S[n]);
        S[++n]=++mx;
    }
    m=0;
    for(int i=1;i<=n;++i)
        S[i]=S[i]-mi+1,m=max(m,S[i]);
    pre_sa(),pre_height();
    int ans=0;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",ans+1);
    return 0;
}

本文标题:【题解】 [SDOI2008]Sandy的卡片 后缀数组.SA luoguP2463

文章作者:Qiuly

发布时间:2019年03月28日 - 00:00

最后更新:2019年03月29日 - 13:53

原始链接:http://qiulyblog.github.io/2019/03/28/[题解]luoguP2463/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。